package codingPractice.huawei;


import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

/**
 * 有N个基站采用链式组网， 按照从左到右编码为1到N编号。
 * 已知定义“业务”概念为三元组（基站起始编号，基站结束编号，利润），意味着需要占据基站起始编号到基站结束编号的所有基站，打通信号流，可以获得对应利润。
 * 现在外部存在多个“业务”需求待接纳，但基站使用具有排他性，也就是说一旦某一个业务占据某个基站，其他业务不可以再使用此基站。
 * 那么接纳哪些业务需求，可以使得利润最大化？
 *
 * 输入
 * 第一行: 输入N，表示有N个基站。 N取值范围[1, 10000]
 * 第二行: 输入M，表示有M组业务。M取值范围[1, 100000]
 * 接下来M行：每行输入三个整数K1 K2 R，以空格隔开，表示起始基站编号，结束基站编号，利润。K1，K2 < N, K1 < K2, R取值范围[1, 100]
 *
 * 输出
 * 输出只有一个整数，表示获取的利润
 */

class Business {
    int start;
    int end;
    int profit;

    public Business(int start, int end, int profit) {
        this.start = start;
        this.end = end;
        this.profit = profit;
    }
}

public class MaxProfit {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            int N = sc.nextInt();
            int M = sc.nextInt();
            Business[] businesses = new Business[M];
            for(int i=0;i<M;i++) {
                businesses[i] = new Business(sc.nextInt(), sc.nextInt(), sc.nextInt());
            }
            int result = getMaxProfit(businesses);
            System.out.println(result);
        }
    }

    //查找不冲突的业务
    private static int findLastNonConflict(Business[] businesses, int index) {
        int low = 0, high = index - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (businesses[mid].end < businesses[index].start) {
                if (businesses[mid + 1].end < businesses[index].start) {
                    low = mid + 1;
                } else {
                    return mid;
                }
            } else {
                high = mid - 1;
            }
        }
        return -1;  //如果没有找到不冲突的业务，返回-1
    }

    //计算最大利润
    public static int getMaxProfit(Business[] businesses) {
        //按结束时间排序
        Arrays.sort(businesses, Comparator.comparingInt(b -> b.end));

        int n = businesses.length;

        //dp[i]表示从第1个业务到第i个业务能获得的最大利润
        int[] dp = new int[n];

        dp[0] = businesses[0].profit;

        //逐个计算每个业务的最大利润
        for(int i=1;i<n;i++) {
            //当前业务的利润
            int includeProfit = businesses[i].profit;

            //查找最近一个不冲突的业务
            int lastNonConflict = findLastNonConflict(businesses, i);
            if (lastNonConflict != -1) {
                includeProfit += dp[lastNonConflict];
            }

            //当前业务的最大利润是，选择当前业务或不选择当前业务的较大者
            dp[i] = Math.max(dp[i-1], includeProfit);
        }

        return dp[n-1];
    }
}
